<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html lang="en">

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <title>LCOV - Lua 5.4.0-alpha - src/ltable.c</title>
  <link rel="stylesheet" type="text/css" href="../gcov.css">
</head>

<body>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="title">LCOV - code coverage report</td></tr>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>

    <tr>
      <td width="100%">
        <table cellpadding=1 border=0 width="100%">
          <tr>
            <td width="10%" class="headerItem">Current view:</td>
            <td width="35%" class="headerValue"><a href="../index.html">top level</a> - <a href="index.html">src</a> - ltable.c</td>
            <td width="5%"></td>
            <td width="15%"></td>
            <td width="10%" class="headerCovTableHead">Hit</td>
            <td width="10%" class="headerCovTableHead">Total</td>
            <td width="15%" class="headerCovTableHead">Coverage</td>
          </tr>
          <tr>
            <td class="headerItem">Test:</td>
            <td class="headerValue">Lua 5.4.0-alpha</td>
            <td></td>
            <td class="headerItem">Lines:</td>
            <td class="headerCovTableEntry">351</td>
            <td class="headerCovTableEntry">377</td>
            <td class="headerCovTableEntryHi">93.1 %</td>
          </tr>
          <tr>
            <td class="headerItem">Date:</td>
            <td class="headerValue">2019-06-13 19:44:19</td>
            <td></td>
          </tr>
          <tr>
            <td class="headerItem">Legend:</td>
            <td class="headerValueLeg">            Lines:
            <span class="coverLegendCov">hit</span>
            <span class="coverLegendNoCov">not hit</span>
</td>
            <td></td>
          </tr>
          <tr><td><img src="../glass.png" width=3 height=3 alt=""></td></tr>
        </table>
      </td>
    </tr>

    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
  </table>

  <table cellpadding=0 cellspacing=0 border=0>
    <tr>
      <td><br></td>
    </tr>
    <tr>
      <td>
<pre class="sourceHeading">          Line data    Source code</pre>
<pre class="source">
<span class="lineNum">       1 </span>            : /*
<span class="lineNum">       2 </span>            : ** $Id: ltable.c $
<span class="lineNum">       3 </span>            : ** Lua tables (hash)
<span class="lineNum">       4 </span>            : ** See Copyright Notice in lua.h
<span class="lineNum">       5 </span>            : */
<span class="lineNum">       6 </span>            : 
<span class="lineNum">       7 </span>            : #define ltable_c
<span class="lineNum">       8 </span>            : #define LUA_CORE
<span class="lineNum">       9 </span>            : 
<span class="lineNum">      10 </span>            : #include &quot;lprefix.h&quot;
<span class="lineNum">      11 </span>            : 
<span class="lineNum">      12 </span>            : 
<span class="lineNum">      13 </span>            : /*
<span class="lineNum">      14 </span>            : ** Implementation of tables (aka arrays, objects, or hash tables).
<span class="lineNum">      15 </span>            : ** Tables keep its elements in two parts: an array part and a hash part.
<span class="lineNum">      16 </span>            : ** Non-negative integer keys are all candidates to be kept in the array
<span class="lineNum">      17 </span>            : ** part. The actual size of the array is the largest 'n' such that
<span class="lineNum">      18 </span>            : ** more than half the slots between 1 and n are in use.
<span class="lineNum">      19 </span>            : ** Hash uses a mix of chained scatter table with Brent's variation.
<span class="lineNum">      20 </span>            : ** A main invariant of these tables is that, if an element is not
<span class="lineNum">      21 </span>            : ** in its main position (i.e. the 'original' position that its hash gives
<span class="lineNum">      22 </span>            : ** to it), then the colliding element is in its own main position.
<span class="lineNum">      23 </span>            : ** Hence even when the load factor reaches 100%, performance remains good.
<span class="lineNum">      24 </span>            : */
<span class="lineNum">      25 </span>            : 
<span class="lineNum">      26 </span>            : #include &lt;math.h&gt;
<span class="lineNum">      27 </span>            : #include &lt;limits.h&gt;
<span class="lineNum">      28 </span>            : 
<span class="lineNum">      29 </span>            : #include &quot;lua.h&quot;
<span class="lineNum">      30 </span>            : 
<span class="lineNum">      31 </span>            : #include &quot;ldebug.h&quot;
<span class="lineNum">      32 </span>            : #include &quot;ldo.h&quot;
<span class="lineNum">      33 </span>            : #include &quot;lgc.h&quot;
<span class="lineNum">      34 </span>            : #include &quot;lmem.h&quot;
<span class="lineNum">      35 </span>            : #include &quot;lobject.h&quot;
<span class="lineNum">      36 </span>            : #include &quot;lstate.h&quot;
<span class="lineNum">      37 </span>            : #include &quot;lstring.h&quot;
<span class="lineNum">      38 </span>            : #include &quot;ltable.h&quot;
<span class="lineNum">      39 </span>            : #include &quot;lvm.h&quot;
<span class="lineNum">      40 </span>            : 
<span class="lineNum">      41 </span>            : 
<span class="lineNum">      42 </span>            : /*
<span class="lineNum">      43 </span>            : ** MAXABITS is the largest integer such that MAXASIZE fits in an
<span class="lineNum">      44 </span>            : ** unsigned int.
<span class="lineNum">      45 </span>            : */
<span class="lineNum">      46 </span>            : #define MAXABITS        cast_int(sizeof(int) * CHAR_BIT - 1)
<span class="lineNum">      47 </span>            : 
<span class="lineNum">      48 </span>            : 
<span class="lineNum">      49 </span>            : /*
<span class="lineNum">      50 </span>            : ** MAXASIZE is the maximum size of the array part. It is the minimum
<span class="lineNum">      51 </span>            : ** between 2^MAXABITS and the maximum size that, measured in bytes,
<span class="lineNum">      52 </span>            : ** fits in a 'size_t'.
<span class="lineNum">      53 </span>            : */
<span class="lineNum">      54 </span>            : #define MAXASIZE        luaM_limitN(1u &lt;&lt; MAXABITS, TValue)
<span class="lineNum">      55 </span>            : 
<span class="lineNum">      56 </span>            : /*
<span class="lineNum">      57 </span>            : ** MAXHBITS is the largest integer such that 2^MAXHBITS fits in a
<span class="lineNum">      58 </span>            : ** signed int.
<span class="lineNum">      59 </span>            : */
<span class="lineNum">      60 </span>            : #define MAXHBITS        (MAXABITS - 1)
<span class="lineNum">      61 </span>            : 
<span class="lineNum">      62 </span>            : 
<span class="lineNum">      63 </span>            : /*
<span class="lineNum">      64 </span>            : ** MAXHSIZE is the maximum size of the hash part. It is the minimum
<span class="lineNum">      65 </span>            : ** between 2^MAXHBITS and the maximum size such that, measured in bytes,
<span class="lineNum">      66 </span>            : ** it fits in a 'size_t'.
<span class="lineNum">      67 </span>            : */
<span class="lineNum">      68 </span>            : #define MAXHSIZE        luaM_limitN(1u &lt;&lt; MAXHBITS, Node)
<span class="lineNum">      69 </span>            : 
<span class="lineNum">      70 </span>            : 
<span class="lineNum">      71 </span>            : #define hashpow2(t,n)           (gnode(t, lmod((n), sizenode(t))))
<span class="lineNum">      72 </span>            : 
<span class="lineNum">      73 </span>            : #define hashstr(t,str)          hashpow2(t, (str)-&gt;hash)
<span class="lineNum">      74 </span>            : #define hashboolean(t,p)        hashpow2(t, p)
<span class="lineNum">      75 </span>            : #define hashint(t,i)            hashpow2(t, i)
<span class="lineNum">      76 </span>            : 
<span class="lineNum">      77 </span>            : 
<span class="lineNum">      78 </span>            : /*
<span class="lineNum">      79 </span>            : ** for some types, it is better to avoid modulus by power of 2, as
<span class="lineNum">      80 </span>            : ** they tend to have many 2 factors.
<span class="lineNum">      81 </span>            : */
<span class="lineNum">      82 </span>            : #define hashmod(t,n)    (gnode(t, ((n) % ((sizenode(t)-1)|1))))
<span class="lineNum">      83 </span>            : 
<span class="lineNum">      84 </span>            : 
<span class="lineNum">      85 </span>            : #define hashpointer(t,p)        hashmod(t, point2uint(p))
<span class="lineNum">      86 </span>            : 
<span class="lineNum">      87 </span>            : 
<span class="lineNum">      88 </span>            : #define dummynode               (&amp;dummynode_)
<span class="lineNum">      89 </span>            : 
<span class="lineNum">      90 </span>            : static const Node dummynode_ = {
<span class="lineNum">      91 </span>            :   {{NULL}, LUA_TEMPTY,  /* value's value and type */
<span class="lineNum">      92 </span>            :    LUA_TNIL, 0, {NULL}}  /* key type, next, and key value */
<span class="lineNum">      93 </span>            : };
<span class="lineNum">      94 </span>            : 
<span class="lineNum">      95 </span>            : 
<span class="lineNum">      96 </span>            : static const TValue absentkey = {ABSTKEYCONSTANT};
<span class="lineNum">      97 </span>            : 
<span class="lineNum">      98 </span>            : 
<span class="lineNum">      99 </span>            : 
<span class="lineNum">     100 </span>            : /*
<span class="lineNum">     101 </span>            : ** Hash for floating-point numbers.
<span class="lineNum">     102 </span>            : ** The main computation should be just
<span class="lineNum">     103 </span>            : **     n = frexp(n, &amp;i); return (n * INT_MAX) + i
<span class="lineNum">     104 </span>            : ** but there are some numerical subtleties.
<span class="lineNum">     105 </span>            : ** In a two-complement representation, INT_MAX does not has an exact
<span class="lineNum">     106 </span>            : ** representation as a float, but INT_MIN does; because the absolute
<span class="lineNum">     107 </span>            : ** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
<span class="lineNum">     108 </span>            : ** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
<span class="lineNum">     109 </span>            : ** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
<span class="lineNum">     110 </span>            : ** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
<span class="lineNum">     111 </span>            : ** INT_MIN.
<span class="lineNum">     112 </span>            : */
<span class="lineNum">     113 </span>            : #if !defined(l_hashfloat)
<span class="lineNum">     114 </span><span class="lineCov">        323 : static int l_hashfloat (lua_Number n) {</span>
<span class="lineNum">     115 </span>            :   int i;
<span class="lineNum">     116 </span>            :   lua_Integer ni;
<span class="lineNum">     117 </span><span class="lineCov">        323 :   n = l_mathop(frexp)(n, &amp;i) * -cast_num(INT_MIN);</span>
<span class="lineNum">     118 </span><span class="lineCov">        323 :   if (!lua_numbertointeger(n, &amp;ni)) {  /* is 'n' inf/-inf/NaN? */</span>
<span class="lineNum">     119 </span>            :     lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
<span class="lineNum">     120 </span><span class="lineCov">          1 :     return 0;</span>
<span class="lineNum">     121 </span>            :   }
<span class="lineNum">     122 </span>            :   else {  /* normal case */
<span class="lineNum">     123 </span><span class="lineCov">        322 :     unsigned int u = cast_uint(i) + cast_uint(ni);</span>
<span class="lineNum">     124 </span><span class="lineCov">        322 :     return cast_int(u &lt;= cast_uint(INT_MAX) ? u : ~u);</span>
<span class="lineNum">     125 </span>            :   }
<span class="lineNum">     126 </span>            : }
<span class="lineNum">     127 </span>            : #endif
<span class="lineNum">     128 </span>            : 
<span class="lineNum">     129 </span>            : 
<span class="lineNum">     130 </span>            : /*
<span class="lineNum">     131 </span>            : ** returns the 'main' position of an element in a table (that is,
<span class="lineNum">     132 </span>            : ** the index of its hash value). The key comes broken (tag in 'ktt'
<span class="lineNum">     133 </span>            : ** and value in 'vkl') so that we can call it on keys inserted into
<span class="lineNum">     134 </span>            : ** nodes.
<span class="lineNum">     135 </span>            : */
<span class="lineNum">     136 </span><span class="lineCov">     116930 : static Node *mainposition (const Table *t, int ktt, const Value *kvl) {</span>
<span class="lineNum">     137 </span><span class="lineCov">     116930 :   switch (withvariant(ktt)) {</span>
<span class="lineNum">     138 </span><span class="lineCov">      24175 :     case LUA_TNUMINT:</span>
<span class="lineNum">     139 </span><span class="lineCov">      24175 :       return hashint(t, ivalueraw(*kvl));</span>
<span class="lineNum">     140 </span><span class="lineCov">        323 :     case LUA_TNUMFLT:</span>
<span class="lineNum">     141 </span><span class="lineCov">        323 :       return hashmod(t, l_hashfloat(fltvalueraw(*kvl)));</span>
<span class="lineNum">     142 </span><span class="lineCov">      88534 :     case LUA_TSHRSTR:</span>
<span class="lineNum">     143 </span><span class="lineCov">      88534 :       return hashstr(t, tsvalueraw(*kvl));</span>
<span class="lineNum">     144 </span><span class="lineCov">       1467 :     case LUA_TLNGSTR:</span>
<span class="lineNum">     145 </span><span class="lineCov">       1467 :       return hashpow2(t, luaS_hashlongstr(tsvalueraw(*kvl)));</span>
<span class="lineNum">     146 </span><span class="lineCov">        603 :     case LUA_TBOOLEAN:</span>
<span class="lineNum">     147 </span><span class="lineCov">        603 :       return hashboolean(t, bvalueraw(*kvl));</span>
<span class="lineNum">     148 </span><span class="lineCov">       1549 :     case LUA_TLIGHTUSERDATA:</span>
<span class="lineNum">     149 </span><span class="lineCov">       1549 :       return hashpointer(t, pvalueraw(*kvl));</span>
<span class="lineNum">     150 </span><span class="lineCov">          5 :     case LUA_TLCF:</span>
<span class="lineNum">     151 </span><span class="lineCov">          5 :       return hashpointer(t, fvalueraw(*kvl));</span>
<span class="lineNum">     152 </span><span class="lineCov">        274 :     default:</span>
<span class="lineNum">     153 </span><span class="lineCov">        274 :       return hashpointer(t, gcvalueraw(*kvl));</span>
<span class="lineNum">     154 </span>            :   }
<span class="lineNum">     155 </span>            : }
<span class="lineNum">     156 </span>            : 
<span class="lineNum">     157 </span>            : 
<span class="lineNum">     158 </span><span class="lineCov">      93105 : static Node *mainpositionTV (const Table *t, const TValue *key) {</span>
<span class="lineNum">     159 </span><span class="lineCov">      93105 :   return mainposition(t, rawtt(key), valraw(key));</span>
<span class="lineNum">     160 </span>            : }
<span class="lineNum">     161 </span>            : 
<span class="lineNum">     162 </span>            : 
<span class="lineNum">     163 </span>            : /*
<span class="lineNum">     164 </span>            : ** Check whether key 'k1' is equal to the key in node 'n2'.
<span class="lineNum">     165 </span>            : ** This equality is raw, so there are no metamethods. Floats
<span class="lineNum">     166 </span>            : ** with integer values have been normalized, so integers cannot
<span class="lineNum">     167 </span>            : ** be equal to floats. It is assumed that 'eqshrstr' is simply
<span class="lineNum">     168 </span>            : ** pointer equality, so that short strings are handled in the
<span class="lineNum">     169 </span>            : ** default case.
<span class="lineNum">     170 </span>            : */
<span class="lineNum">     171 </span><span class="lineCov">       6947 : static int equalkey (const TValue *k1, const Node *n2) {</span>
<span class="lineNum">     172 </span><span class="lineCov">       6947 :   if (rawtt(k1) != keytt(n2))  /* not the same variants? */</span>
<span class="lineNum">     173 </span><span class="lineCov">       2251 :    return 0;  /* cannot be same key */</span>
<span class="lineNum">     174 </span><span class="lineCov">       4696 :   switch (ttypetag(k1)) {</span>
<span class="lineNum">     175 </span><span class="lineNoCov">          0 :     case LUA_TNIL:</span>
<span class="lineNum">     176 </span><span class="lineNoCov">          0 :       return 1;</span>
<span class="lineNum">     177 </span><span class="lineNoCov">          0 :     case LUA_TNUMINT:</span>
<span class="lineNum">     178 </span><span class="lineNoCov">          0 :       return (ivalue(k1) == keyival(n2));</span>
<span class="lineNum">     179 </span><span class="lineCov">         56 :     case LUA_TNUMFLT:</span>
<span class="lineNum">     180 </span><span class="lineCov">         56 :       return luai_numeq(fltvalue(k1), fltvalueraw(keyval(n2)));</span>
<span class="lineNum">     181 </span><span class="lineCov">         55 :     case LUA_TBOOLEAN:</span>
<span class="lineNum">     182 </span><span class="lineCov">         55 :       return bvalue(k1) == bvalueraw(keyval(n2));</span>
<span class="lineNum">     183 </span><span class="lineCov">        304 :     case LUA_TLIGHTUSERDATA:</span>
<span class="lineNum">     184 </span><span class="lineCov">        304 :       return pvalue(k1) == pvalueraw(keyval(n2));</span>
<span class="lineNum">     185 </span><span class="lineCov">          1 :     case LUA_TLCF:</span>
<span class="lineNum">     186 </span><span class="lineCov">          1 :       return fvalue(k1) == fvalueraw(keyval(n2));</span>
<span class="lineNum">     187 </span><span class="lineCov">        595 :     case LUA_TLNGSTR:</span>
<span class="lineNum">     188 </span><span class="lineCov">        595 :       return luaS_eqlngstr(tsvalue(k1), keystrval(n2));</span>
<span class="lineNum">     189 </span><span class="lineCov">       3685 :     default:</span>
<span class="lineNum">     190 </span><span class="lineCov">       3685 :       return gcvalue(k1) == gcvalueraw(keyval(n2));</span>
<span class="lineNum">     191 </span>            :   }
<span class="lineNum">     192 </span>            : }
<span class="lineNum">     193 </span>            : 
<span class="lineNum">     194 </span>            : 
<span class="lineNum">     195 </span>            : /*
<span class="lineNum">     196 </span>            : ** True if value of 'alimit' is equal to the real size of the array
<span class="lineNum">     197 </span>            : ** part of table 't'. (Otherwise, the array part must be larger than
<span class="lineNum">     198 </span>            : ** 'alimit'.)
<span class="lineNum">     199 </span>            : */
<span class="lineNum">     200 </span>            : #define limitequalsasize(t)     (isrealasize(t) || ispow2((t)-&gt;alimit))
<span class="lineNum">     201 </span>            : 
<span class="lineNum">     202 </span>            : 
<span class="lineNum">     203 </span>            : /*
<span class="lineNum">     204 </span>            : ** Returns the real size of the 'array' array
<span class="lineNum">     205 </span>            : */
<span class="lineNum">     206 </span><span class="lineCov">      76755 : LUAI_FUNC unsigned int luaH_realasize (const Table *t) {</span>
<span class="lineNum">     207 </span><span class="lineCov">      76755 :   if (limitequalsasize(t))</span>
<span class="lineNum">     208 </span><span class="lineCov">      70837 :     return t-&gt;alimit;  /* this is the size */</span>
<span class="lineNum">     209 </span>            :   else {
<span class="lineNum">     210 </span><span class="lineCov">       5918 :     unsigned int size = t-&gt;alimit;</span>
<span class="lineNum">     211 </span>            :     /* compute the smallest power of 2 not smaller than 'n' */
<span class="lineNum">     212 </span><span class="lineCov">       5918 :     size |= (size &gt;&gt; 1);</span>
<span class="lineNum">     213 </span><span class="lineCov">       5918 :     size |= (size &gt;&gt; 2);</span>
<span class="lineNum">     214 </span><span class="lineCov">       5918 :     size |= (size &gt;&gt; 4);</span>
<span class="lineNum">     215 </span><span class="lineCov">       5918 :     size |= (size &gt;&gt; 8);</span>
<span class="lineNum">     216 </span><span class="lineCov">       5918 :     size |= (size &gt;&gt; 16);</span>
<span class="lineNum">     217 </span>            : #if (UINT_MAX &gt;&gt; 30) &gt; 3
<span class="lineNum">     218 </span>            :     size |= (size &gt;&gt; 32);  /* unsigned int has more than 32 bits */
<span class="lineNum">     219 </span>            : #endif
<span class="lineNum">     220 </span><span class="lineCov">       5918 :     size++;</span>
<span class="lineNum">     221 </span>            :     lua_assert(ispow2(size) &amp;&amp; size/2 &lt; t-&gt;alimit &amp;&amp; t-&gt;alimit &lt; size);
<span class="lineNum">     222 </span><span class="lineCov">       5918 :     return size;</span>
<span class="lineNum">     223 </span>            :   }
<span class="lineNum">     224 </span>            : }
<span class="lineNum">     225 </span>            : 
<span class="lineNum">     226 </span>            : 
<span class="lineNum">     227 </span>            : /*
<span class="lineNum">     228 </span>            : ** Check whether real size of the array is a power of 2.
<span class="lineNum">     229 </span>            : ** (If it is not, 'alimit' cannot be changed to any other value
<span class="lineNum">     230 </span>            : ** without changing the real size.)
<span class="lineNum">     231 </span>            : */
<span class="lineNum">     232 </span><span class="lineCov">      11880 : static int ispow2realasize (const Table *t) {</span>
<span class="lineNum">     233 </span><span class="lineCov">      11880 :   return (!isrealasize(t) || ispow2(t-&gt;alimit));</span>
<span class="lineNum">     234 </span>            : }
<span class="lineNum">     235 </span>            : 
<span class="lineNum">     236 </span>            : 
<span class="lineNum">     237 </span><span class="lineCov">      57913 : static unsigned int setlimittosize (Table *t) {</span>
<span class="lineNum">     238 </span><span class="lineCov">      57913 :   t-&gt;alimit = luaH_realasize(t);</span>
<span class="lineNum">     239 </span><span class="lineCov">      57913 :   setrealasize(t);</span>
<span class="lineNum">     240 </span><span class="lineCov">      57913 :   return t-&gt;alimit;</span>
<span class="lineNum">     241 </span>            : }
<span class="lineNum">     242 </span>            : 
<span class="lineNum">     243 </span>            : 
<span class="lineNum">     244 </span>            : #define limitasasize(t) check_exp(isrealasize(t), t-&gt;alimit)
<span class="lineNum">     245 </span>            : 
<span class="lineNum">     246 </span>            : 
<span class="lineNum">     247 </span>            : 
<span class="lineNum">     248 </span>            : /*
<span class="lineNum">     249 </span>            : ** &quot;Generic&quot; get version. (Not that generic: not valid for integers,
<span class="lineNum">     250 </span>            : ** which may be in array part, nor for floats with integral values.)
<span class="lineNum">     251 </span>            : */
<span class="lineNum">     252 </span><span class="lineCov">       5065 : static const TValue *getgeneric (Table *t, const TValue *key) {</span>
<span class="lineNum">     253 </span><span class="lineCov">       5065 :   Node *n = mainpositionTV(t, key);</span>
<span class="lineNum">     254 </span>            :   for (;;) {  /* check whether 'key' is somewhere in the chain */
<span class="lineNum">     255 </span><span class="lineCov">       6947 :     if (equalkey(key, n))</span>
<span class="lineNum">     256 </span><span class="lineCov">       3747 :       return gval(n);  /* that's it */</span>
<span class="lineNum">     257 </span>            :     else {
<span class="lineNum">     258 </span><span class="lineCov">       3200 :       int nx = gnext(n);</span>
<span class="lineNum">     259 </span><span class="lineCov">       3200 :       if (nx == 0)</span>
<span class="lineNum">     260 </span><span class="lineCov">       1318 :         return &amp;absentkey;  /* not found */</span>
<span class="lineNum">     261 </span><span class="lineCov">       1882 :       n += nx;</span>
<span class="lineNum">     262 </span>            :     }
<span class="lineNum">     263 </span>            :   }
<span class="lineNum">     264 </span>            : }
<span class="lineNum">     265 </span>            : 
<span class="lineNum">     266 </span>            : 
<span class="lineNum">     267 </span>            : /*
<span class="lineNum">     268 </span>            : ** returns the index for 'k' if 'k' is an appropriate key to live in
<span class="lineNum">     269 </span>            : ** the array part of a table, 0 otherwise.
<span class="lineNum">     270 </span>            : */
<span class="lineNum">     271 </span><span class="lineCov">      23902 : static unsigned int arrayindex (lua_Integer k) {</span>
<span class="lineNum">     272 </span><span class="lineCov">      23902 :   if (l_castS2U(k) - 1u &lt; MAXASIZE)  /* 'k' in [1, MAXASIZE]? */</span>
<span class="lineNum">     273 </span><span class="lineCov">      23896 :     return cast_uint(k);  /* 'key' is an appropriate array index */</span>
<span class="lineNum">     274 </span>            :   else
<span class="lineNum">     275 </span><span class="lineCov">          6 :     return 0;</span>
<span class="lineNum">     276 </span>            : }
<span class="lineNum">     277 </span>            : 
<span class="lineNum">     278 </span>            : 
<span class="lineNum">     279 </span>            : /*
<span class="lineNum">     280 </span>            : ** returns the index of a 'key' for table traversals. First goes all
<span class="lineNum">     281 </span>            : ** elements in the array part, then elements in the hash part. The
<span class="lineNum">     282 </span>            : ** beginning of a traversal is signaled by 0.
<span class="lineNum">     283 </span>            : */
<span class="lineNum">     284 </span><span class="lineCov">       2783 : static unsigned int findindex (lua_State *L, Table *t, TValue *key,</span>
<span class="lineNum">     285 </span>            :                                unsigned int asize) {
<span class="lineNum">     286 </span>            :   unsigned int i;
<span class="lineNum">     287 </span><span class="lineCov">       2783 :   if (ttisnil(key)) return 0;  /* first iteration */</span>
<span class="lineNum">     288 </span><span class="lineCov">       2597 :   i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0;</span>
<span class="lineNum">     289 </span><span class="lineCov">       2597 :   if (i - 1u &lt; asize)  /* is 'key' inside array part? */</span>
<span class="lineNum">     290 </span><span class="lineCov">         18 :     return i;  /* yes; that's the index */</span>
<span class="lineNum">     291 </span>            :   else {
<span class="lineNum">     292 </span><span class="lineCov">       2579 :     const TValue *n = getgeneric(t, key);</span>
<span class="lineNum">     293 </span><span class="lineCov">       2579 :     if (unlikely(isabstkey(n)))</span>
<span class="lineNum">     294 </span><span class="lineCov">          1 :       luaG_runerror(L, &quot;invalid key to 'next'&quot;);  /* key not found */</span>
<span class="lineNum">     295 </span><span class="lineCov">       2578 :     i = cast_int(nodefromval(n) - gnode(t, 0));  /* key index in hash table */</span>
<span class="lineNum">     296 </span>            :     /* hash elements are numbered after array ones */
<span class="lineNum">     297 </span><span class="lineCov">       2578 :     return (i + 1) + asize;</span>
<span class="lineNum">     298 </span>            :   }
<span class="lineNum">     299 </span>            : }
<span class="lineNum">     300 </span>            : 
<span class="lineNum">     301 </span>            : 
<span class="lineNum">     302 </span><span class="lineCov">       2783 : int luaH_next (lua_State *L, Table *t, StkId key) {</span>
<span class="lineNum">     303 </span><span class="lineCov">       2783 :   unsigned int asize = luaH_realasize(t);</span>
<span class="lineNum">     304 </span><span class="lineCov">       2783 :   unsigned int i = findindex(L, t, s2v(key), asize);  /* find original key */</span>
<span class="lineNum">     305 </span><span class="lineCov">       2782 :   for (; i &lt; asize; i++) {  /* try first array part */</span>
<span class="lineNum">     306 </span><span class="lineCov">         17 :     if (!isempty(&amp;t-&gt;array[i])) {  /* a non-empty entry? */</span>
<span class="lineNum">     307 </span><span class="lineCov">         17 :       setivalue(s2v(key), i + 1);</span>
<span class="lineNum">     308 </span><span class="lineCov">         17 :       setobj2s(L, key + 1, &amp;t-&gt;array[i]);</span>
<span class="lineNum">     309 </span><span class="lineCov">         17 :       return 1;</span>
<span class="lineNum">     310 </span>            :     }
<span class="lineNum">     311 </span>            :   }
<span class="lineNum">     312 </span><span class="lineCov">       3904 :   for (i -= asize; cast_int(i) &lt; sizenode(t); i++) {  /* hash part */</span>
<span class="lineNum">     313 </span><span class="lineCov">       3729 :     if (!isempty(gval(gnode(t, i)))) {  /* a non-empty entry? */</span>
<span class="lineNum">     314 </span><span class="lineCov">       2590 :       Node *n = gnode(t, i);</span>
<span class="lineNum">     315 </span><span class="lineCov">       2590 :       getnodekey(L, s2v(key), n);</span>
<span class="lineNum">     316 </span><span class="lineCov">       2590 :       setobj2s(L, key + 1, gval(n));</span>
<span class="lineNum">     317 </span><span class="lineCov">       2590 :       return 1;</span>
<span class="lineNum">     318 </span>            :     }
<span class="lineNum">     319 </span>            :   }
<span class="lineNum">     320 </span><span class="lineCov">        175 :   return 0;  /* no more elements */</span>
<span class="lineNum">     321 </span>            : }
<span class="lineNum">     322 </span>            : 
<span class="lineNum">     323 </span>            : 
<span class="lineNum">     324 </span><span class="lineCov">      38547 : static void freehash (lua_State *L, Table *t) {</span>
<span class="lineNum">     325 </span><span class="lineCov">      38547 :   if (!isdummy(t))</span>
<span class="lineNum">     326 </span><span class="lineCov">       5299 :     luaM_freearray(L, t-&gt;node, cast_sizet(sizenode(t)));</span>
<span class="lineNum">     327 </span><span class="lineCov">      38547 : }</span>
<span class="lineNum">     328 </span>            : 
<span class="lineNum">     329 </span>            : 
<span class="lineNum">     330 </span>            : /*
<span class="lineNum">     331 </span>            : ** {=============================================================
<span class="lineNum">     332 </span>            : ** Rehash
<span class="lineNum">     333 </span>            : ** ==============================================================
<span class="lineNum">     334 </span>            : */
<span class="lineNum">     335 </span>            : 
<span class="lineNum">     336 </span>            : /*
<span class="lineNum">     337 </span>            : ** Compute the optimal size for the array part of table 't'. 'nums' is a
<span class="lineNum">     338 </span>            : ** &quot;count array&quot; where 'nums[i]' is the number of integers in the table
<span class="lineNum">     339 </span>            : ** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
<span class="lineNum">     340 </span>            : ** integer keys in the table and leaves with the number of keys that
<span class="lineNum">     341 </span>            : ** will go to the array part; return the optimal size.  (The condition
<span class="lineNum">     342 </span>            : ** 'twotoi &gt; 0' in the for loop stops the loop if 'twotoi' overflows.)
<span class="lineNum">     343 </span>            : */
<span class="lineNum">     344 </span><span class="lineCov">      28036 : static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {</span>
<span class="lineNum">     345 </span>            :   int i;
<span class="lineNum">     346 </span>            :   unsigned int twotoi;  /* 2^i (candidate for optimal size) */
<span class="lineNum">     347 </span><span class="lineCov">      28036 :   unsigned int a = 0;  /* number of elements smaller than 2^i */</span>
<span class="lineNum">     348 </span><span class="lineCov">      28036 :   unsigned int na = 0;  /* number of elements to go to array part */</span>
<span class="lineNum">     349 </span><span class="lineCov">      28036 :   unsigned int optimal = 0;  /* optimal size for array part */</span>
<span class="lineNum">     350 </span>            :   /* loop while keys can fill more than half of total size */
<span class="lineNum">     351 </span><span class="lineCov">      88804 :   for (i = 0, twotoi = 1;</span>
<span class="lineNum">     352 </span><span class="lineCov">      88804 :        twotoi &gt; 0 &amp;&amp; *pna &gt; twotoi / 2;</span>
<span class="lineNum">     353 </span><span class="lineCov">      60768 :        i++, twotoi *= 2) {</span>
<span class="lineNum">     354 </span><span class="lineCov">      60768 :     a += nums[i];</span>
<span class="lineNum">     355 </span><span class="lineCov">      60768 :     if (a &gt; twotoi/2) {  /* more than half elements present? */</span>
<span class="lineNum">     356 </span><span class="lineCov">      60750 :       optimal = twotoi;  /* optimal size (till now) */</span>
<span class="lineNum">     357 </span><span class="lineCov">      60750 :       na = a;  /* all elements up to 'optimal' will go to array part */</span>
<span class="lineNum">     358 </span>            :     }
<span class="lineNum">     359 </span>            :   }
<span class="lineNum">     360 </span>            :   lua_assert((optimal == 0 || optimal / 2 &lt; na) &amp;&amp; na &lt;= optimal);
<span class="lineNum">     361 </span><span class="lineCov">      28036 :   *pna = na;</span>
<span class="lineNum">     362 </span><span class="lineCov">      28036 :   return optimal;</span>
<span class="lineNum">     363 </span>            : }
<span class="lineNum">     364 </span>            : 
<span class="lineNum">     365 </span>            : 
<span class="lineNum">     366 </span><span class="lineCov">      23883 : static int countint (lua_Integer key, unsigned int *nums) {</span>
<span class="lineNum">     367 </span><span class="lineCov">      23883 :   unsigned int k = arrayindex(key);</span>
<span class="lineNum">     368 </span><span class="lineCov">      23883 :   if (k != 0) {  /* is 'key' an appropriate array index? */</span>
<span class="lineNum">     369 </span><span class="lineCov">      23877 :     nums[luaO_ceillog2(k)]++;  /* count as such */</span>
<span class="lineNum">     370 </span><span class="lineCov">      23877 :     return 1;</span>
<span class="lineNum">     371 </span>            :   }
<span class="lineNum">     372 </span>            :   else
<span class="lineNum">     373 </span><span class="lineCov">          6 :     return 0;</span>
<span class="lineNum">     374 </span>            : }
<span class="lineNum">     375 </span>            : 
<span class="lineNum">     376 </span>            : 
<span class="lineNum">     377 </span>            : /*
<span class="lineNum">     378 </span>            : ** Count keys in array part of table 't': Fill 'nums[i]' with
<span class="lineNum">     379 </span>            : ** number of keys that will go into corresponding slice and return
<span class="lineNum">     380 </span>            : ** total number of non-nil keys.
<span class="lineNum">     381 </span>            : */
<span class="lineNum">     382 </span><span class="lineCov">      28036 : static unsigned int numusearray (const Table *t, unsigned int *nums) {</span>
<span class="lineNum">     383 </span>            :   int lg;
<span class="lineNum">     384 </span>            :   unsigned int ttlg;  /* 2^lg */
<span class="lineNum">     385 </span><span class="lineCov">      28036 :   unsigned int ause = 0;  /* summation of 'nums' */</span>
<span class="lineNum">     386 </span><span class="lineCov">      28036 :   unsigned int i = 1;  /* count to traverse all array keys */</span>
<span class="lineNum">     387 </span><span class="lineCov">      28036 :   unsigned int asize = limitasasize(t);  /* real array size */</span>
<span class="lineNum">     388 </span>            :   /* traverse each slice */
<span class="lineNum">     389 </span><span class="lineCov">      64931 :   for (lg = 0, ttlg = 1; lg &lt;= MAXABITS; lg++, ttlg *= 2) {</span>
<span class="lineNum">     390 </span><span class="lineCov">      64931 :     unsigned int lc = 0;  /* counter */</span>
<span class="lineNum">     391 </span><span class="lineCov">      64931 :     unsigned int lim = ttlg;</span>
<span class="lineNum">     392 </span><span class="lineCov">      64931 :     if (lim &gt; asize) {</span>
<span class="lineNum">     393 </span><span class="lineCov">      28040 :       lim = asize;  /* adjust upper limit */</span>
<span class="lineNum">     394 </span><span class="lineCov">      28040 :       if (i &gt; lim)</span>
<span class="lineNum">     395 </span><span class="lineCov">      28036 :         break;  /* no more elements to count */</span>
<span class="lineNum">     396 </span>            :     }
<span class="lineNum">     397 </span>            :     /* count elements in range (2^(lg - 1), 2^lg] */
<span class="lineNum">     398 </span><span class="lineCov">      82042 :     for (; i &lt;= lim; i++) {</span>
<span class="lineNum">     399 </span><span class="lineCov">      45147 :       if (!isempty(&amp;t-&gt;array[i-1]))</span>
<span class="lineNum">     400 </span><span class="lineCov">      44767 :         lc++;</span>
<span class="lineNum">     401 </span>            :     }
<span class="lineNum">     402 </span><span class="lineCov">      36895 :     nums[lg] += lc;</span>
<span class="lineNum">     403 </span><span class="lineCov">      36895 :     ause += lc;</span>
<span class="lineNum">     404 </span>            :   }
<span class="lineNum">     405 </span><span class="lineCov">      28036 :   return ause;</span>
<span class="lineNum">     406 </span>            : }
<span class="lineNum">     407 </span>            : 
<span class="lineNum">     408 </span>            : 
<span class="lineNum">     409 </span><span class="lineCov">      28036 : static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {</span>
<span class="lineNum">     410 </span><span class="lineCov">      28036 :   int totaluse = 0;  /* total number of elements */</span>
<span class="lineNum">     411 </span><span class="lineCov">      28036 :   int ause = 0;  /* elements added to 'nums' (can go to array part) */</span>
<span class="lineNum">     412 </span><span class="lineCov">      28036 :   int i = sizenode(t);</span>
<span class="lineNum">     413 </span><span class="lineCov">      79820 :   while (i--) {</span>
<span class="lineNum">     414 </span><span class="lineCov">      51784 :     Node *n = &amp;t-&gt;node[i];</span>
<span class="lineNum">     415 </span><span class="lineCov">      51784 :     if (!isempty(gval(n))) {</span>
<span class="lineNum">     416 </span><span class="lineCov">      27147 :       if (keyisinteger(n))</span>
<span class="lineNum">     417 </span><span class="lineCov">         14 :         ause += countint(keyival(n), nums);</span>
<span class="lineNum">     418 </span><span class="lineCov">      27147 :       totaluse++;</span>
<span class="lineNum">     419 </span>            :     }
<span class="lineNum">     420 </span>            :   }
<span class="lineNum">     421 </span><span class="lineCov">      28036 :   *pna += ause;</span>
<span class="lineNum">     422 </span><span class="lineCov">      28036 :   return totaluse;</span>
<span class="lineNum">     423 </span>            : }
<span class="lineNum">     424 </span>            : 
<span class="lineNum">     425 </span>            : 
<span class="lineNum">     426 </span>            : /*
<span class="lineNum">     427 </span>            : ** Creates an array for the hash part of a table with the given
<span class="lineNum">     428 </span>            : ** size, or reuses the dummy node if size is zero.
<span class="lineNum">     429 </span>            : ** The computation for size overflow is in two steps: the first
<span class="lineNum">     430 </span>            : ** comparison ensures that the shift in the second one does not
<span class="lineNum">     431 </span>            : ** overflow.
<span class="lineNum">     432 </span>            : */
<span class="lineNum">     433 </span><span class="lineCov">      38743 : static void setnodevector (lua_State *L, Table *t, unsigned int size) {</span>
<span class="lineNum">     434 </span><span class="lineCov">      38743 :   if (size == 0) {  /* no elements to hash part? */</span>
<span class="lineNum">     435 </span><span class="lineCov">      33289 :     t-&gt;node = cast(Node *, dummynode);  /* use common 'dummynode' */</span>
<span class="lineNum">     436 </span><span class="lineCov">      33289 :     t-&gt;lsizenode = 0;</span>
<span class="lineNum">     437 </span><span class="lineCov">      33289 :     t-&gt;lastfree = NULL;  /* signal that it is using dummy node */</span>
<span class="lineNum">     438 </span>            :   }
<span class="lineNum">     439 </span>            :   else {
<span class="lineNum">     440 </span>            :     int i;
<span class="lineNum">     441 </span><span class="lineCov">       5454 :     int lsize = luaO_ceillog2(size);</span>
<span class="lineNum">     442 </span><span class="lineCov">       5454 :     if (lsize &gt; MAXHBITS || (1u &lt;&lt; lsize) &gt; MAXHSIZE)</span>
<span class="lineNum">     443 </span><span class="lineNoCov">          0 :       luaG_runerror(L, &quot;table overflow&quot;);</span>
<span class="lineNum">     444 </span><span class="lineCov">       5454 :     size = twoto(lsize);</span>
<span class="lineNum">     445 </span><span class="lineCov">       5454 :     t-&gt;node = luaM_newvector(L, size, Node);</span>
<span class="lineNum">     446 </span><span class="lineCov">      78480 :     for (i = 0; i &lt; (int)size; i++) {</span>
<span class="lineNum">     447 </span><span class="lineCov">      73026 :       Node *n = gnode(t, i);</span>
<span class="lineNum">     448 </span><span class="lineCov">      73026 :       gnext(n) = 0;</span>
<span class="lineNum">     449 </span><span class="lineCov">      73026 :       setnilkey(n);</span>
<span class="lineNum">     450 </span><span class="lineCov">      73026 :       setempty(gval(n));</span>
<span class="lineNum">     451 </span>            :     }
<span class="lineNum">     452 </span><span class="lineCov">       5454 :     t-&gt;lsizenode = cast_byte(lsize);</span>
<span class="lineNum">     453 </span><span class="lineCov">       5454 :     t-&gt;lastfree = gnode(t, size);  /* all positions are free */</span>
<span class="lineNum">     454 </span>            :   }
<span class="lineNum">     455 </span><span class="lineCov">      38743 : }</span>
<span class="lineNum">     456 </span>            : 
<span class="lineNum">     457 </span>            : 
<span class="lineNum">     458 </span>            : /*
<span class="lineNum">     459 </span>            : ** (Re)insert all elements from the hash part of 'ot' into table 't'.
<span class="lineNum">     460 </span>            : */
<span class="lineNum">     461 </span><span class="lineCov">      29877 : static void reinsert (lua_State *L, Table *ot, Table *t) {</span>
<span class="lineNum">     462 </span>            :   int j;
<span class="lineNum">     463 </span><span class="lineCov">      29877 :   int size = sizenode(ot);</span>
<span class="lineNum">     464 </span><span class="lineCov">      83502 :   for (j = 0; j &lt; size; j++) {</span>
<span class="lineNum">     465 </span><span class="lineCov">      53625 :     Node *old = gnode(ot, j);</span>
<span class="lineNum">     466 </span><span class="lineCov">      53625 :     if (!isempty(gval(old))) {</span>
<span class="lineNum">     467 </span>            :       /* doesn't need barrier/invalidate cache, as entry was
<span class="lineNum">     468 </span>            :          already present in the table */
<span class="lineNum">     469 </span>            :       TValue k;
<span class="lineNum">     470 </span><span class="lineCov">      27147 :       getnodekey(L, &amp;k, old);</span>
<span class="lineNum">     471 </span><span class="lineCov">      27147 :       setobjt2t(L, luaH_set(L, t, &amp;k), gval(old));</span>
<span class="lineNum">     472 </span>            :     }
<span class="lineNum">     473 </span>            :   }
<span class="lineNum">     474 </span><span class="lineCov">      29877 : }</span>
<span class="lineNum">     475 </span>            : 
<span class="lineNum">     476 </span>            : 
<span class="lineNum">     477 </span>            : /*
<span class="lineNum">     478 </span>            : ** Exchange the hash part of 't1' and 't2'.
<span class="lineNum">     479 </span>            : */
<span class="lineNum">     480 </span><span class="lineCov">      29877 : static void exchangehashpart (Table *t1, Table *t2) {</span>
<span class="lineNum">     481 </span><span class="lineCov">      29877 :   lu_byte lsizenode = t1-&gt;lsizenode;</span>
<span class="lineNum">     482 </span><span class="lineCov">      29877 :   Node *node = t1-&gt;node;</span>
<span class="lineNum">     483 </span><span class="lineCov">      29877 :   Node *lastfree = t1-&gt;lastfree;</span>
<span class="lineNum">     484 </span><span class="lineCov">      29877 :   t1-&gt;lsizenode = t2-&gt;lsizenode;</span>
<span class="lineNum">     485 </span><span class="lineCov">      29877 :   t1-&gt;node = t2-&gt;node;</span>
<span class="lineNum">     486 </span><span class="lineCov">      29877 :   t1-&gt;lastfree = t2-&gt;lastfree;</span>
<span class="lineNum">     487 </span><span class="lineCov">      29877 :   t2-&gt;lsizenode = lsizenode;</span>
<span class="lineNum">     488 </span><span class="lineCov">      29877 :   t2-&gt;node = node;</span>
<span class="lineNum">     489 </span><span class="lineCov">      29877 :   t2-&gt;lastfree = lastfree;</span>
<span class="lineNum">     490 </span><span class="lineCov">      29877 : }</span>
<span class="lineNum">     491 </span>            : 
<span class="lineNum">     492 </span>            : 
<span class="lineNum">     493 </span>            : /*
<span class="lineNum">     494 </span>            : ** Resize table 't' for the new given sizes. Both allocations (for
<span class="lineNum">     495 </span>            : ** the hash part and for the array part) can fail, which creates some
<span class="lineNum">     496 </span>            : ** subtleties. If the first allocation, for the hash part, fails, an
<span class="lineNum">     497 </span>            : ** error is raised and that is it. Otherwise, it copies the elements from
<span class="lineNum">     498 </span>            : ** the shrinking part of the array (if it is shrinking) into the new
<span class="lineNum">     499 </span>            : ** hash. Then it reallocates the array part.  If that fails, the table
<span class="lineNum">     500 </span>            : ** is in its original state; the function frees the new hash part and then
<span class="lineNum">     501 </span>            : ** raises the allocation error. Otherwise, it sets the new hash part
<span class="lineNum">     502 </span>            : ** into the table, initializes the new part of the array (if any) with
<span class="lineNum">     503 </span>            : ** nils and reinserts the elements of the old hash back into the new
<span class="lineNum">     504 </span>            : ** parts of the table.
<span class="lineNum">     505 </span>            : */
<span class="lineNum">     506 </span><span class="lineCov">      29877 : void luaH_resize (lua_State *L, Table *t, unsigned int newasize,</span>
<span class="lineNum">     507 </span>            :                                           unsigned int nhsize) {
<span class="lineNum">     508 </span>            :   unsigned int i;
<span class="lineNum">     509 </span>            :   Table newt;  /* to keep the new hash part */
<span class="lineNum">     510 </span><span class="lineCov">      29877 :   unsigned int oldasize = setlimittosize(t);</span>
<span class="lineNum">     511 </span>            :   TValue *newarray;
<span class="lineNum">     512 </span>            :   /* create new hash part with appropriate size into 'newt' */
<span class="lineNum">     513 </span><span class="lineCov">      29877 :   setnodevector(L, &amp;newt, nhsize);</span>
<span class="lineNum">     514 </span><span class="lineCov">      29877 :   if (newasize &lt; oldasize) {  /* will array shrink? */</span>
<span class="lineNum">     515 </span><span class="lineNoCov">          0 :     t-&gt;alimit = newasize;  /* pretend array has new size... */</span>
<span class="lineNum">     516 </span><span class="lineNoCov">          0 :     exchangehashpart(t, &amp;newt);  /* and new hash */</span>
<span class="lineNum">     517 </span>            :     /* re-insert into the new hash the elements from vanishing slice */
<span class="lineNum">     518 </span><span class="lineNoCov">          0 :     for (i = newasize; i &lt; oldasize; i++) {</span>
<span class="lineNum">     519 </span><span class="lineNoCov">          0 :       if (!isempty(&amp;t-&gt;array[i]))</span>
<span class="lineNum">     520 </span><span class="lineNoCov">          0 :         luaH_setint(L, t, i + 1, &amp;t-&gt;array[i]);</span>
<span class="lineNum">     521 </span>            :     }
<span class="lineNum">     522 </span><span class="lineNoCov">          0 :     t-&gt;alimit = oldasize;  /* restore current size... */</span>
<span class="lineNum">     523 </span><span class="lineNoCov">          0 :     exchangehashpart(t, &amp;newt);  /* and hash (in case of errors) */</span>
<span class="lineNum">     524 </span>            :   }
<span class="lineNum">     525 </span>            :   /* allocate new array */
<span class="lineNum">     526 </span><span class="lineCov">      29877 :   newarray = luaM_reallocvector(L, t-&gt;array, oldasize, newasize, TValue);</span>
<span class="lineNum">     527 </span><span class="lineCov">      29877 :   if (unlikely(newarray == NULL &amp;&amp; newasize &gt; 0)) {  /* allocation failed? */</span>
<span class="lineNum">     528 </span><span class="lineNoCov">          0 :     freehash(L, &amp;newt);  /* release new hash part */</span>
<span class="lineNum">     529 </span><span class="lineNoCov">          0 :     luaM_error(L);  /* raise error (with array unchanged) */</span>
<span class="lineNum">     530 </span>            :   }
<span class="lineNum">     531 </span>            :   /* allocation ok; initialize new part of the array */
<span class="lineNum">     532 </span><span class="lineCov">      29877 :   exchangehashpart(t, &amp;newt);  /* 't' has the new hash ('newt' has the old) */</span>
<span class="lineNum">     533 </span><span class="lineCov">      29877 :   t-&gt;array = newarray;  /* set new array part */</span>
<span class="lineNum">     534 </span><span class="lineCov">      29877 :   t-&gt;alimit = newasize;</span>
<span class="lineNum">     535 </span><span class="lineCov">      80228 :   for (i = oldasize; i &lt; newasize; i++)  /* clear new slice of the array */</span>
<span class="lineNum">     536 </span><span class="lineCov">      50351 :      setempty(&amp;t-&gt;array[i]);</span>
<span class="lineNum">     537 </span>            :   /* re-insert elements from old hash part into new parts */
<span class="lineNum">     538 </span><span class="lineCov">      29877 :   reinsert(L, &amp;newt, t);  /* 'newt' now has the old hash */</span>
<span class="lineNum">     539 </span><span class="lineCov">      29877 :   freehash(L, &amp;newt);  /* free old hash part */</span>
<span class="lineNum">     540 </span><span class="lineCov">      29877 : }</span>
<span class="lineNum">     541 </span>            : 
<span class="lineNum">     542 </span>            : 
<span class="lineNum">     543 </span><span class="lineCov">        221 : void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize) {</span>
<span class="lineNum">     544 </span><span class="lineCov">        221 :   int nsize = allocsizenode(t);</span>
<span class="lineNum">     545 </span><span class="lineCov">        221 :   luaH_resize(L, t, nasize, nsize);</span>
<span class="lineNum">     546 </span><span class="lineCov">        221 : }</span>
<span class="lineNum">     547 </span>            : 
<span class="lineNum">     548 </span>            : /*
<span class="lineNum">     549 </span>            : ** nums[i] = number of keys 'k' where 2^(i - 1) &lt; k &lt;= 2^i
<span class="lineNum">     550 </span>            : */
<span class="lineNum">     551 </span><span class="lineCov">      28036 : static void rehash (lua_State *L, Table *t, const TValue *ek) {</span>
<span class="lineNum">     552 </span>            :   unsigned int asize;  /* optimal size for array part */
<span class="lineNum">     553 </span>            :   unsigned int na;  /* number of keys in the array part */
<span class="lineNum">     554 </span>            :   unsigned int nums[MAXABITS + 1];
<span class="lineNum">     555 </span>            :   int i;
<span class="lineNum">     556 </span>            :   int totaluse;
<span class="lineNum">     557 </span><span class="lineCov">     925188 :   for (i = 0; i &lt;= MAXABITS; i++) nums[i] = 0;  /* reset counts */</span>
<span class="lineNum">     558 </span><span class="lineCov">      28036 :   setlimittosize(t);</span>
<span class="lineNum">     559 </span><span class="lineCov">      28036 :   na = numusearray(t, nums);  /* count keys in array part */</span>
<span class="lineNum">     560 </span><span class="lineCov">      28036 :   totaluse = na;  /* all those keys are integer keys */</span>
<span class="lineNum">     561 </span><span class="lineCov">      28036 :   totaluse += numusehash(t, nums, &amp;na);  /* count keys in hash part */</span>
<span class="lineNum">     562 </span>            :   /* count extra key */
<span class="lineNum">     563 </span><span class="lineCov">      28036 :   if (ttisinteger(ek))</span>
<span class="lineNum">     564 </span><span class="lineCov">      23869 :     na += countint(ivalue(ek), nums);</span>
<span class="lineNum">     565 </span><span class="lineCov">      28036 :   totaluse++;</span>
<span class="lineNum">     566 </span>            :   /* compute new size for array part */
<span class="lineNum">     567 </span><span class="lineCov">      28036 :   asize = computesizes(nums, &amp;na);</span>
<span class="lineNum">     568 </span>            :   /* resize the table to new computed sizes */
<span class="lineNum">     569 </span><span class="lineCov">      28036 :   luaH_resize(L, t, asize, totaluse - na);</span>
<span class="lineNum">     570 </span><span class="lineCov">      28036 : }</span>
<span class="lineNum">     571 </span>            : 
<span class="lineNum">     572 </span>            : 
<span class="lineNum">     573 </span>            : 
<span class="lineNum">     574 </span>            : /*
<span class="lineNum">     575 </span>            : ** }=============================================================
<span class="lineNum">     576 </span>            : */
<span class="lineNum">     577 </span>            : 
<span class="lineNum">     578 </span>            : 
<span class="lineNum">     579 </span><span class="lineCov">       8866 : Table *luaH_new (lua_State *L) {</span>
<span class="lineNum">     580 </span><span class="lineCov">       8866 :   GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));</span>
<span class="lineNum">     581 </span><span class="lineCov">       8866 :   Table *t = gco2t(o);</span>
<span class="lineNum">     582 </span><span class="lineCov">       8866 :   t-&gt;metatable = NULL;</span>
<span class="lineNum">     583 </span><span class="lineCov">       8866 :   t-&gt;flags = cast_byte(~0);</span>
<span class="lineNum">     584 </span><span class="lineCov">       8866 :   t-&gt;array = NULL;</span>
<span class="lineNum">     585 </span><span class="lineCov">       8866 :   t-&gt;alimit = 0;</span>
<span class="lineNum">     586 </span><span class="lineCov">       8866 :   setnodevector(L, t, 0);</span>
<span class="lineNum">     587 </span><span class="lineCov">       8866 :   return t;</span>
<span class="lineNum">     588 </span>            : }
<span class="lineNum">     589 </span>            : 
<span class="lineNum">     590 </span>            : 
<span class="lineNum">     591 </span><span class="lineCov">       8670 : void luaH_free (lua_State *L, Table *t) {</span>
<span class="lineNum">     592 </span><span class="lineCov">       8670 :   freehash(L, t);</span>
<span class="lineNum">     593 </span><span class="lineCov">       8670 :   luaM_freearray(L, t-&gt;array, luaH_realasize(t));</span>
<span class="lineNum">     594 </span><span class="lineCov">       8670 :   luaM_free(L, t);</span>
<span class="lineNum">     595 </span><span class="lineCov">       8670 : }</span>
<span class="lineNum">     596 </span>            : 
<span class="lineNum">     597 </span>            : 
<span class="lineNum">     598 </span><span class="lineCov">      51861 : static Node *getfreepos (Table *t) {</span>
<span class="lineNum">     599 </span><span class="lineCov">      51861 :   if (!isdummy(t)) {</span>
<span class="lineNum">     600 </span><span class="lineCov">      49496 :     while (t-&gt;lastfree &gt; t-&gt;node) {</span>
<span class="lineNum">     601 </span><span class="lineCov">      46097 :       t-&gt;lastfree--;</span>
<span class="lineNum">     602 </span><span class="lineCov">      46097 :       if (keyisnil(t-&gt;lastfree))</span>
<span class="lineNum">     603 </span><span class="lineCov">      23825 :         return t-&gt;lastfree;</span>
<span class="lineNum">     604 </span>            :     }
<span class="lineNum">     605 </span>            :   }
<span class="lineNum">     606 </span><span class="lineCov">      28036 :   return NULL;  /* could not find a free place */</span>
<span class="lineNum">     607 </span>            : }
<span class="lineNum">     608 </span>            : 
<span class="lineNum">     609 </span>            : 
<span class="lineNum">     610 </span>            : 
<span class="lineNum">     611 </span>            : /*
<span class="lineNum">     612 </span>            : ** inserts a new key into a hash table; first, check whether key's main
<span class="lineNum">     613 </span>            : ** position is free. If not, check whether colliding node is in its main
<span class="lineNum">     614 </span>            : ** position or not: if it is not, move colliding node to an empty place and
<span class="lineNum">     615 </span>            : ** put new key in its main position; otherwise (colliding node is in its main
<span class="lineNum">     616 </span>            : ** position), new key goes to an empty position.
<span class="lineNum">     617 </span>            : */
<span class="lineNum">     618 </span><span class="lineCov">      88043 : TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {</span>
<span class="lineNum">     619 </span>            :   Node *mp;
<span class="lineNum">     620 </span>            :   TValue aux;
<span class="lineNum">     621 </span><span class="lineCov">      88043 :   if (unlikely(ttisnil(key)))</span>
<span class="lineNum">     622 </span><span class="lineCov">          2 :     luaG_runerror(L, &quot;table index is nil&quot;);</span>
<span class="lineNum">     623 </span><span class="lineCov">      88041 :   else if (ttisfloat(key)) {</span>
<span class="lineNum">     624 </span><span class="lineCov">        123 :     lua_Number f = fltvalue(key);</span>
<span class="lineNum">     625 </span>            :     lua_Integer k;
<span class="lineNum">     626 </span><span class="lineCov">        123 :     if (luaV_flttointeger(f, &amp;k, 0)) {  /* does key fit in an integer? */</span>
<span class="lineNum">     627 </span><span class="lineCov">          8 :       setivalue(&amp;aux, k);</span>
<span class="lineNum">     628 </span><span class="lineCov">          8 :       key = &amp;aux;  /* insert it as an integer */</span>
<span class="lineNum">     629 </span>            :     }
<span class="lineNum">     630 </span><span class="lineCov">        115 :     else if (unlikely(luai_numisnan(f)))</span>
<span class="lineNum">     631 </span><span class="lineCov">          1 :       luaG_runerror(L, &quot;table index is NaN&quot;);</span>
<span class="lineNum">     632 </span>            :   }
<span class="lineNum">     633 </span><span class="lineCov">      88040 :   mp = mainpositionTV(t, key);</span>
<span class="lineNum">     634 </span><span class="lineCov">      88040 :   if (!isempty(gval(mp)) || isdummy(t)) {  /* main position is taken? */</span>
<span class="lineNum">     635 </span>            :     Node *othern;
<span class="lineNum">     636 </span><span class="lineCov">      51861 :     Node *f = getfreepos(t);  /* get a free place */</span>
<span class="lineNum">     637 </span><span class="lineCov">      51861 :     if (f == NULL) {  /* cannot find a free place? */</span>
<span class="lineNum">     638 </span><span class="lineCov">      28036 :       rehash(L, t, key);  /* grow table */</span>
<span class="lineNum">     639 </span>            :       /* whatever called 'newkey' takes care of TM cache */
<span class="lineNum">     640 </span><span class="lineCov">      28036 :       return luaH_set(L, t, key);  /* insert key into grown table */</span>
<span class="lineNum">     641 </span>            :     }
<span class="lineNum">     642 </span>            :     lua_assert(!isdummy(t));
<span class="lineNum">     643 </span><span class="lineCov">      23825 :     othern = mainposition(t, keytt(mp), &amp;keyval(mp));</span>
<span class="lineNum">     644 </span><span class="lineCov">      23825 :     if (othern != mp) {  /* is colliding node out of its main position? */</span>
<span class="lineNum">     645 </span>            :       /* yes; move colliding node into free position */
<span class="lineNum">     646 </span><span class="lineCov">       6324 :       while (othern + gnext(othern) != mp)  /* find previous */</span>
<span class="lineNum">     647 </span><span class="lineCov">       1388 :         othern += gnext(othern);</span>
<span class="lineNum">     648 </span><span class="lineCov">       4936 :       gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */</span>
<span class="lineNum">     649 </span><span class="lineCov">       4936 :       *f = *mp;  /* copy colliding node into free pos. (mp-&gt;next also goes) */</span>
<span class="lineNum">     650 </span><span class="lineCov">       4936 :       if (gnext(mp) != 0) {</span>
<span class="lineNum">     651 </span><span class="lineCov">        805 :         gnext(f) += cast_int(mp - f);  /* correct 'next' */</span>
<span class="lineNum">     652 </span><span class="lineCov">        805 :         gnext(mp) = 0;  /* now 'mp' is free */</span>
<span class="lineNum">     653 </span>            :       }
<span class="lineNum">     654 </span><span class="lineCov">       4936 :       setempty(gval(mp));</span>
<span class="lineNum">     655 </span>            :     }
<span class="lineNum">     656 </span>            :     else {  /* colliding node is in its own main position */
<span class="lineNum">     657 </span>            :       /* new node will go into free position */
<span class="lineNum">     658 </span><span class="lineCov">      18889 :       if (gnext(mp) != 0)</span>
<span class="lineNum">     659 </span><span class="lineCov">       4763 :         gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */</span>
<span class="lineNum">     660 </span>            :       else lua_assert(gnext(f) == 0);
<span class="lineNum">     661 </span><span class="lineCov">      18889 :       gnext(mp) = cast_int(f - mp);</span>
<span class="lineNum">     662 </span><span class="lineCov">      18889 :       mp = f;</span>
<span class="lineNum">     663 </span>            :     }
<span class="lineNum">     664 </span>            :   }
<span class="lineNum">     665 </span><span class="lineCov">      60004 :   setnodekey(L, mp, key);</span>
<span class="lineNum">     666 </span><span class="lineCov">      60004 :   luaC_barrierback(L, obj2gco(t), key);</span>
<span class="lineNum">     667 </span>            :   lua_assert(isempty(gval(mp)));
<span class="lineNum">     668 </span><span class="lineCov">      60004 :   return gval(mp);</span>
<span class="lineNum">     669 </span>            : }
<span class="lineNum">     670 </span>            : 
<span class="lineNum">     671 </span>            : 
<span class="lineNum">     672 </span>            : /*
<span class="lineNum">     673 </span>            : ** Search function for integers. If integer is inside 'alimit', get it
<span class="lineNum">     674 </span>            : ** directly from the array part. Otherwise, if 'alimit' is not equal to
<span class="lineNum">     675 </span>            : ** the real size of the array, key still can be in the array part. In
<span class="lineNum">     676 </span>            : ** this case, try to avoid a call to 'luaH_realasize' when key is just
<span class="lineNum">     677 </span>            : ** one more than the limit (so that it can be incremented without
<span class="lineNum">     678 </span>            : ** changing the real size of the array).
<span class="lineNum">     679 </span>            : */
<span class="lineNum">     680 </span><span class="lineCov">      57257 : const TValue *luaH_getint (Table *t, lua_Integer key) {</span>
<span class="lineNum">     681 </span><span class="lineCov">      57257 :   if (l_castS2U(key) - 1u &lt; t-&gt;alimit)  /* 'key' in [1, t-&gt;alimit]? */</span>
<span class="lineNum">     682 </span><span class="lineCov">      26674 :     return &amp;t-&gt;array[key - 1];</span>
<span class="lineNum">     683 </span><span class="lineCov">      30583 :   else if (!limitequalsasize(t) &amp;&amp;  /* key still may be in the array part? */</span>
<span class="lineNum">     684 </span><span class="lineCov">       5933 :            (l_castS2U(key) == t-&gt;alimit + 1 ||</span>
<span class="lineNum">     685 </span><span class="lineNoCov">          0 :             l_castS2U(key) - 1u &lt; luaH_realasize(t))) {</span>
<span class="lineNum">     686 </span><span class="lineCov">       5933 :     t-&gt;alimit = cast_uint(key);  /* probably '#t' is here now */</span>
<span class="lineNum">     687 </span><span class="lineCov">       5933 :     return &amp;t-&gt;array[key - 1];</span>
<span class="lineNum">     688 </span>            :   }
<span class="lineNum">     689 </span>            :   else {
<span class="lineNum">     690 </span><span class="lineCov">      24650 :     Node *n = hashint(t, key);</span>
<span class="lineNum">     691 </span>            :     for (;;) {  /* check whether 'key' is somewhere in the chain */
<span class="lineNum">     692 </span><span class="lineCov">      24659 :       if (keyisinteger(n) &amp;&amp; keyival(n) == key)</span>
<span class="lineNum">     693 </span><span class="lineCov">         43 :         return gval(n);  /* that's it */</span>
<span class="lineNum">     694 </span>            :       else {
<span class="lineNum">     695 </span><span class="lineCov">      24616 :         int nx = gnext(n);</span>
<span class="lineNum">     696 </span><span class="lineCov">      24616 :         if (nx == 0) break;</span>
<span class="lineNum">     697 </span><span class="lineCov">          9 :         n += nx;</span>
<span class="lineNum">     698 </span>            :       }
<span class="lineNum">     699 </span>            :     }
<span class="lineNum">     700 </span><span class="lineCov">      24607 :     return &amp;absentkey;</span>
<span class="lineNum">     701 </span>            :   }
<span class="lineNum">     702 </span>            : }
<span class="lineNum">     703 </span>            : 
<span class="lineNum">     704 </span>            : 
<span class="lineNum">     705 </span>            : /*
<span class="lineNum">     706 </span>            : ** search function for short strings
<span class="lineNum">     707 </span>            : */
<span class="lineNum">     708 </span><span class="lineCov">     221221 : const TValue *luaH_getshortstr (Table *t, TString *key) {</span>
<span class="lineNum">     709 </span><span class="lineCov">     221221 :   Node *n = hashstr(t, key);</span>
<span class="lineNum">     710 </span>            :   lua_assert(key-&gt;tt == LUA_TSHRSTR);
<span class="lineNum">     711 </span>            :   for (;;) {  /* check whether 'key' is somewhere in the chain */
<span class="lineNum">     712 </span><span class="lineCov">     286556 :     if (keyisshrstr(n) &amp;&amp; eqshrstr(keystrval(n), key))</span>
<span class="lineNum">     713 </span><span class="lineCov">     153814 :       return gval(n);  /* that's it */</span>
<span class="lineNum">     714 </span>            :     else {
<span class="lineNum">     715 </span><span class="lineCov">     132742 :       int nx = gnext(n);</span>
<span class="lineNum">     716 </span><span class="lineCov">     132742 :       if (nx == 0)</span>
<span class="lineNum">     717 </span><span class="lineCov">      67407 :         return &amp;absentkey;  /* not found */</span>
<span class="lineNum">     718 </span><span class="lineCov">      65335 :       n += nx;</span>
<span class="lineNum">     719 </span>            :     }
<span class="lineNum">     720 </span>            :   }
<span class="lineNum">     721 </span>            : }
<span class="lineNum">     722 </span>            : 
<span class="lineNum">     723 </span>            : 
<span class="lineNum">     724 </span><span class="lineCov">      24153 : const TValue *luaH_getstr (Table *t, TString *key) {</span>
<span class="lineNum">     725 </span><span class="lineCov">      24153 :   if (key-&gt;tt == LUA_TSHRSTR)</span>
<span class="lineNum">     726 </span><span class="lineCov">      24153 :     return luaH_getshortstr(t, key);</span>
<span class="lineNum">     727 </span>            :   else {  /* for long strings, use generic case */
<span class="lineNum">     728 </span>            :     TValue ko;
<span class="lineNum">     729 </span><span class="lineNoCov">          0 :     setsvalue(cast(lua_State *, NULL), &amp;ko, key);</span>
<span class="lineNum">     730 </span><span class="lineNoCov">          0 :     return getgeneric(t, &amp;ko);</span>
<span class="lineNum">     731 </span>            :   }
<span class="lineNum">     732 </span>            : }
<span class="lineNum">     733 </span>            : 
<span class="lineNum">     734 </span>            : 
<span class="lineNum">     735 </span>            : /*
<span class="lineNum">     736 </span>            : ** main search function
<span class="lineNum">     737 </span>            : */
<span class="lineNum">     738 </span><span class="lineCov">     133103 : const TValue *luaH_get (Table *t, const TValue *key) {</span>
<span class="lineNum">     739 </span><span class="lineCov">     133103 :   switch (ttypetag(key)) {</span>
<span class="lineNum">     740 </span><span class="lineCov">     106715 :     case LUA_TSHRSTR: return luaH_getshortstr(t, tsvalue(key));</span>
<span class="lineNum">     741 </span><span class="lineCov">      23889 :     case LUA_TNUMINT: return luaH_getint(t, ivalue(key));</span>
<span class="lineNum">     742 </span><span class="lineCov">          4 :     case LUA_TNIL: return &amp;absentkey;</span>
<span class="lineNum">     743 </span><span class="lineCov">        166 :     case LUA_TNUMFLT: {</span>
<span class="lineNum">     744 </span>            :       lua_Integer k;
<span class="lineNum">     745 </span><span class="lineCov">        175 :       if (luaV_flttointeger(fltvalue(key), &amp;k, 0)) /* index is an integral? */</span>
<span class="lineNum">     746 </span><span class="lineCov">          9 :         return luaH_getint(t, k);  /* use specialized version */</span>
<span class="lineNum">     747 </span>            :       /* else... */
<span class="lineNum">     748 </span>            :     }  /* FALLTHROUGH */
<span class="lineNum">     749 </span>            :     default:
<span class="lineNum">     750 </span><span class="lineCov">       2486 :       return getgeneric(t, key);</span>
<span class="lineNum">     751 </span>            :   }
<span class="lineNum">     752 </span>            : }
<span class="lineNum">     753 </span>            : 
<span class="lineNum">     754 </span>            : 
<span class="lineNum">     755 </span>            : /*
<span class="lineNum">     756 </span>            : ** beware: when using this function you probably need to check a GC
<span class="lineNum">     757 </span>            : ** barrier and invalidate the TM cache.
<span class="lineNum">     758 </span>            : */
<span class="lineNum">     759 </span><span class="lineCov">     122224 : TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {</span>
<span class="lineNum">     760 </span><span class="lineCov">     122224 :   const TValue *p = luaH_get(t, key);</span>
<span class="lineNum">     761 </span><span class="lineCov">     122224 :   if (!isabstkey(p))</span>
<span class="lineNum">     762 </span><span class="lineCov">      77235 :     return cast(TValue *, p);</span>
<span class="lineNum">     763 </span><span class="lineCov">      44989 :   else return luaH_newkey(L, t, key);</span>
<span class="lineNum">     764 </span>            : }
<span class="lineNum">     765 </span>            : 
<span class="lineNum">     766 </span>            : 
<span class="lineNum">     767 </span><span class="lineCov">       1022 : void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) {</span>
<span class="lineNum">     768 </span><span class="lineCov">       1022 :   const TValue *p = luaH_getint(t, key);</span>
<span class="lineNum">     769 </span>            :   TValue *cell;
<span class="lineNum">     770 </span><span class="lineCov">       1022 :   if (!isabstkey(p))</span>
<span class="lineNum">     771 </span><span class="lineCov">        654 :     cell = cast(TValue *, p);</span>
<span class="lineNum">     772 </span>            :   else {
<span class="lineNum">     773 </span>            :     TValue k;
<span class="lineNum">     774 </span><span class="lineCov">        368 :     setivalue(&amp;k, key);</span>
<span class="lineNum">     775 </span><span class="lineCov">        368 :     cell = luaH_newkey(L, t, &amp;k);</span>
<span class="lineNum">     776 </span>            :   }
<span class="lineNum">     777 </span><span class="lineCov">       1022 :   setobj2t(L, cell, value);</span>
<span class="lineNum">     778 </span><span class="lineCov">       1022 : }</span>
<span class="lineNum">     779 </span>            : 
<span class="lineNum">     780 </span>            : 
<span class="lineNum">     781 </span>            : /*
<span class="lineNum">     782 </span>            : ** Try to find a boundary in the hash part of table 't'. From the
<span class="lineNum">     783 </span>            : ** caller, we know that 'j' is zero or present and that 'j + 1' is
<span class="lineNum">     784 </span>            : ** present. We want to find a larger key that is absent from the
<span class="lineNum">     785 </span>            : ** table, so that we can do a binary search between the two keys to
<span class="lineNum">     786 </span>            : ** find a boundary. We keep doubling 'j' until we get an absent index.
<span class="lineNum">     787 </span>            : ** If the doubling would overflow, we try LUA_MAXINTEGER. If it is
<span class="lineNum">     788 </span>            : ** absent, we are ready for the binary search. ('j', being max integer,
<span class="lineNum">     789 </span>            : ** is larger or equal to 'i', but it cannot be equal because it is
<span class="lineNum">     790 </span>            : ** absent while 'i' is present; so 'j &gt; i'.) Otherwise, 'j' is a
<span class="lineNum">     791 </span>            : ** boundary. ('j + 1' cannot be a present integer key because it is
<span class="lineNum">     792 </span>            : ** not a valid integer in Lua.)
<span class="lineNum">     793 </span>            : */
<span class="lineNum">     794 </span><span class="lineCov">          1 : static lua_Unsigned hash_search (Table *t, lua_Unsigned j) {</span>
<span class="lineNum">     795 </span>            :   lua_Unsigned i;
<span class="lineNum">     796 </span><span class="lineCov">          1 :   if (j == 0) j++;  /* the caller ensures 'j + 1' is present */</span>
<span class="lineNum">     797 </span>            :   do {
<span class="lineNum">     798 </span><span class="lineCov">          1 :     i = j;  /* 'i' is a present index */</span>
<span class="lineNum">     799 </span><span class="lineCov">          1 :     if (j &lt;= l_castS2U(LUA_MAXINTEGER) / 2)</span>
<span class="lineNum">     800 </span><span class="lineCov">          1 :       j *= 2;</span>
<span class="lineNum">     801 </span>            :     else {
<span class="lineNum">     802 </span><span class="lineNoCov">          0 :       j = LUA_MAXINTEGER;</span>
<span class="lineNum">     803 </span><span class="lineNoCov">          0 :       if (isempty(luaH_getint(t, j)))  /* t[j] not present? */</span>
<span class="lineNum">     804 </span><span class="lineNoCov">          0 :         break;  /* 'j' now is an absent index */</span>
<span class="lineNum">     805 </span>            :       else  /* weird case */
<span class="lineNum">     806 </span><span class="lineNoCov">          0 :         return j;  /* well, max integer is a boundary... */</span>
<span class="lineNum">     807 </span>            :     }
<span class="lineNum">     808 </span><span class="lineCov">          1 :   } while (!isempty(luaH_getint(t, j)));  /* repeat until an absent t[j] */</span>
<span class="lineNum">     809 </span>            :   /* i &lt; j  &amp;&amp;  t[i] present  &amp;&amp;  t[j] absent */
<span class="lineNum">     810 </span><span class="lineCov">          3 :   while (j - i &gt; 1u) {  /* do a binary search between them */</span>
<span class="lineNum">     811 </span><span class="lineCov">          2 :     lua_Unsigned m = (i + j) / 2;</span>
<span class="lineNum">     812 </span><span class="lineCov">          2 :     if (isempty(luaH_getint(t, m))) j = m;</span>
<span class="lineNum">     813 </span><span class="lineCov">          1 :     else i = m;</span>
<span class="lineNum">     814 </span>            :   }
<span class="lineNum">     815 </span><span class="lineCov">          1 :   return i;</span>
<span class="lineNum">     816 </span>            : }
<span class="lineNum">     817 </span>            : 
<span class="lineNum">     818 </span>            : 
<span class="lineNum">     819 </span><span class="lineCov">        916 : static unsigned int binsearch (const TValue *array, unsigned int i,</span>
<span class="lineNum">     820 </span>            :                                                     unsigned int j) {
<span class="lineNum">     821 </span><span class="lineCov">       3512 :   while (j - i &gt; 1u) {  /* binary search */</span>
<span class="lineNum">     822 </span><span class="lineCov">       2596 :     unsigned int m = (i + j) / 2;</span>
<span class="lineNum">     823 </span><span class="lineCov">       2596 :     if (isempty(&amp;array[m - 1])) j = m;</span>
<span class="lineNum">     824 </span><span class="lineCov">       1730 :     else i = m;</span>
<span class="lineNum">     825 </span>            :   }
<span class="lineNum">     826 </span><span class="lineCov">        916 :   return i;</span>
<span class="lineNum">     827 </span>            : }
<span class="lineNum">     828 </span>            : 
<span class="lineNum">     829 </span>            : 
<span class="lineNum">     830 </span>            : /*
<span class="lineNum">     831 </span>            : ** Try to find a boundary in table 't'. (A 'boundary' is an integer index
<span class="lineNum">     832 </span>            : ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent
<span class="lineNum">     833 </span>            : ** and 'maxinteger' if t[maxinteger] is present.)
<span class="lineNum">     834 </span>            : ** (In the next explanation, we use Lua indices, that is, with base 1.
<span class="lineNum">     835 </span>            : ** The code itself uses base 0 when indexing the array part of the table.)
<span class="lineNum">     836 </span>            : ** The code starts with 'limit', a position in the array part that may
<span class="lineNum">     837 </span>            : ** be a boundary.
<span class="lineNum">     838 </span>            : ** (1) If 't[limit]' is empty, there must be a boundary before it.
<span class="lineNum">     839 </span>            : ** As a common case (e.g., after 't[#t]=nil'), check whether 'hint-1'
<span class="lineNum">     840 </span>            : ** is present. If so, it is a boundary. Otherwise, do a binary search
<span class="lineNum">     841 </span>            : ** between 0 and limit to find a boundary. In both cases, try to
<span class="lineNum">     842 </span>            : ** use this boundary as the new 'limit', as a hint for the next call.
<span class="lineNum">     843 </span>            : ** (2) If 't[limit]' is not empty and the array has more elements
<span class="lineNum">     844 </span>            : ** after 'limit', try to find a boundary there. Again, try first
<span class="lineNum">     845 </span>            : ** the special case (which should be quite frequent) where 'limit+1'
<span class="lineNum">     846 </span>            : ** is empty, so that 'limit' is a boundary. Otherwise, check the
<span class="lineNum">     847 </span>            : ** last element of the array part (set it as a new limit). If it is empty,
<span class="lineNum">     848 </span>            : ** there must be a boundary between the old limit (present) and the new
<span class="lineNum">     849 </span>            : ** limit (absent), which is found with a binary search. (This boundary
<span class="lineNum">     850 </span>            : ** always can be a new limit.)
<span class="lineNum">     851 </span>            : ** (3) The last case is when there are no elements in the array part
<span class="lineNum">     852 </span>            : ** (limit == 0) or its last element (the new limit) is present.
<span class="lineNum">     853 </span>            : ** In this case, must check the hash part. If there is no hash part,
<span class="lineNum">     854 </span>            : ** the boundary is 0. Otherwise, if 'limit+1' is absent, 'limit' is
<span class="lineNum">     855 </span>            : ** a boundary. Finally, if 'limit+1' is present, call 'hash_search'
<span class="lineNum">     856 </span>            : ** to find a boundary in the hash part of the table. (In those
<span class="lineNum">     857 </span>            : ** cases, the boundary is not inside the array part, and therefore
<span class="lineNum">     858 </span>            : ** cannot be used as a new limit.)
<span class="lineNum">     859 </span>            : */
<span class="lineNum">     860 </span><span class="lineCov">      18874 : lua_Unsigned luaH_getn (Table *t) {</span>
<span class="lineNum">     861 </span><span class="lineCov">      18874 :   unsigned int limit = t-&gt;alimit;</span>
<span class="lineNum">     862 </span><span class="lineCov">      18874 :   if (limit &gt; 0 &amp;&amp; isempty(&amp;t-&gt;array[limit - 1])) {</span>
<span class="lineNum">     863 </span>            :     /* (1) there must be a boundary before 'limit' */
<span class="lineNum">     864 </span><span class="lineCov">      11880 :     if (limit &gt;= 2 &amp;&amp; !isempty(&amp;t-&gt;array[limit - 2])) {</span>
<span class="lineNum">     865 </span>            :       /* 'limit - 1' is a boundary; can it be a new limit? */
<span class="lineNum">     866 </span><span class="lineCov">      10964 :       if (ispow2realasize(t) &amp;&amp; !ispow2(limit - 1)) {</span>
<span class="lineNum">     867 </span><span class="lineCov">      10960 :         t-&gt;alimit = limit - 1;</span>
<span class="lineNum">     868 </span><span class="lineCov">      10960 :         setnorealasize(t);</span>
<span class="lineNum">     869 </span>            :       }
<span class="lineNum">     870 </span><span class="lineCov">      10964 :       return limit - 1;</span>
<span class="lineNum">     871 </span>            :     }
<span class="lineNum">     872 </span>            :     else {  /* must search for a boundary in [0, limit] */
<span class="lineNum">     873 </span><span class="lineCov">        916 :       unsigned int boundary = binsearch(t-&gt;array, 0, limit);</span>
<span class="lineNum">     874 </span>            :       /* can this boundary represent the real size of the array? */
<span class="lineNum">     875 </span><span class="lineCov">        916 :       if (ispow2realasize(t) &amp;&amp; boundary &gt; luaH_realasize(t) / 2) {</span>
<span class="lineNum">     876 </span><span class="lineCov">        856 :         t-&gt;alimit = boundary;  /* use it as the new limit */</span>
<span class="lineNum">     877 </span><span class="lineCov">        856 :         setnorealasize(t);</span>
<span class="lineNum">     878 </span>            :       }
<span class="lineNum">     879 </span><span class="lineCov">        916 :       return boundary;</span>
<span class="lineNum">     880 </span>            :     }
<span class="lineNum">     881 </span>            :   }
<span class="lineNum">     882 </span>            :   /* 'limit' is zero or present in table */
<span class="lineNum">     883 </span><span class="lineCov">       6994 :   if (!limitequalsasize(t)) {</span>
<span class="lineNum">     884 </span>            :     /* (2) 'limit' &gt; 0 and array has more elements after 'limit' */
<span class="lineNum">     885 </span><span class="lineCov">       5920 :     if (isempty(&amp;t-&gt;array[limit]))  /* 'limit + 1' is empty? */</span>
<span class="lineNum">     886 </span><span class="lineCov">       5920 :       return limit;  /* this is the boundary */</span>
<span class="lineNum">     887 </span>            :     /* else, try last element in the array */
<span class="lineNum">     888 </span><span class="lineNoCov">          0 :     limit = luaH_realasize(t);</span>
<span class="lineNum">     889 </span><span class="lineNoCov">          0 :     if (isempty(&amp;t-&gt;array[limit - 1])) {  /* empty? */</span>
<span class="lineNum">     890 </span>            :       /* there must be a boundary in the array after old limit,
<span class="lineNum">     891 </span>            :          and it must be a valid new limit */
<span class="lineNum">     892 </span><span class="lineNoCov">          0 :       unsigned int boundary = binsearch(t-&gt;array, t-&gt;alimit, limit);</span>
<span class="lineNum">     893 </span><span class="lineNoCov">          0 :       t-&gt;alimit = boundary;</span>
<span class="lineNum">     894 </span><span class="lineNoCov">          0 :       return boundary;</span>
<span class="lineNum">     895 </span>            :     }
<span class="lineNum">     896 </span>            :     /* else, new limit is present in the table; check the hash part */
<span class="lineNum">     897 </span>            :   }
<span class="lineNum">     898 </span>            :   /* (3) 'limit' is the last element and either is zero or present in table */
<span class="lineNum">     899 </span>            :   lua_assert(limit == luaH_realasize(t) &amp;&amp;
<span class="lineNum">     900 </span>            :              (limit == 0 || !isempty(&amp;t-&gt;array[limit - 1])));
<span class="lineNum">     901 </span><span class="lineCov">       1074 :   if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1))))</span>
<span class="lineNum">     902 </span><span class="lineCov">       1073 :     return limit;  /* 'limit + 1' is absent... */</span>
<span class="lineNum">     903 </span>            :   else  /* 'limit + 1' is also present */
<span class="lineNum">     904 </span><span class="lineCov">          1 :     return hash_search(t, limit);</span>
<span class="lineNum">     905 </span>            : }
<span class="lineNum">     906 </span>            : 
<span class="lineNum">     907 </span>            : 
<span class="lineNum">     908 </span>            : 
<span class="lineNum">     909 </span>            : #if defined(LUA_DEBUG)
<span class="lineNum">     910 </span>            : 
<span class="lineNum">     911 </span>            : Node *luaH_mainposition (const Table *t, const TValue *key) {
<span class="lineNum">     912 </span>            :   return mainpositionTV(t, key);
<span class="lineNum">     913 </span>            : }
<span class="lineNum">     914 </span>            : 
<span class="lineNum">     915 </span>            : int luaH_isdummy (const Table *t) { return isdummy(t); }
<span class="lineNum">     916 </span>            : 
<span class="lineNum">     917 </span>            : #endif
</pre>
      </td>
    </tr>
  </table>
  <br>

  <table width="100%" border=0 cellspacing=0 cellpadding=0>
    <tr><td class="ruler"><img src="../glass.png" width=3 height=3 alt=""></td></tr>
    <tr><td class="versionInfo">Generated by: <a href="http://ltp.sourceforge.net/coverage/lcov.php" target="_parent">LCOV version 1.13</a></td></tr>
  </table>
  <br>

</body>
</html>
